import numpy as np
class Util:
    def __init__(self):
        self.trans_proba = {'ns': 1, 'nb': 1, 'bm': 1, 'be': 1, 'mm': 1, 'me': 1, 'en': 1, 'eb': 1}
        self.trans_proba = {i:np.log(j) for i,j in self.trans_proba.iteritems()}

    def viterbi(self, nodes):
        paths = nodes[0]
        for l in range(1, len(nodes)):
            paths_ = paths.copy()
            paths = {}
            for i in nodes[l]:
                nows = {}
                for j in paths_:
                    if j[-1]+i in self.trans_proba:
                        nows[j+i] = paths_[j] + nodes[l][i] + self.trans_proba[j[-1]+i]
                k = np.argmax(nows.values())
                paths[nows.keys()[k]] = nows.values()[k]
        return paths.keys()[np.argmax(paths.values())]